<head>
    <meta charset="UTF-8">
<title>算法提高 vertex cover</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
给定一个N个点M条边的无向图G（点的编号从1至N），问是否存在一个不超过K个点的集合S，使得G中的每条边都至少有一个点在集合S中。<br />
【输入格式】<br />
输入的第一行包含一个整数T，表示数据的组数。<br />
接下来T组数据中：每组输入的第一行包含三个整数n, m, k，分别表示图的点数，边数，集合点数的最大值。接下来m行，每行2个正整数x，y，表示编号为 x 的节点与编号为 y 的节点间有一条边相连。<br />
【输出格式】<br />
对于每组测试数据，若其存在解，则将解输出出来：第一行为一个整数t，表示所选点集的大小；第二行为t个整数，表示所选的点的编号。如果存在多组解，只要输出其中一种方案即可（会有special judge程序对你的输出进行检查）。<br />
若该组测试数据不包含解，则输出一个数-1（一行）。<br />
【样例输入】<br />
2<br />
10 8 3<br />
6 4<br />
7 2<br />
7 4<br />
7 6<br />
9 3<br />
9 5<br />
10 6<br />
10 9<br />
10 8 2<br />
6 4<br />
7 2<br />
7 4<br />
7 6<br />
9 3<br />
9 5<br />
10 6<br />
10 9<br />
【样例输出】<br />
3<br />
6 7 9<br />
-1<br />
【数据规模和约定】</p>
<p>对于80%的数据，满足&nbsp;0&lt;n&lt;=20, m&lt;=200, k&lt;=20。<br />
所有的数据满足 0&lt;n&lt;=100, m&lt;=5000, k&lt;=20。</p>